\documentclass[a4paper, 12pt]{article}


\usepackage[francais]{babel}	% Langue
\usepackage[utf8]{inputenc}	% Encodage du texte
\usepackage[T1]{fontenc}		% Encodage de police
\usepackage{lmodern}			% Police

%\usepackage{textcomp}		% Symboles
%\usepackage{url}			% URLs
\usepackage{graphicx}		% Images
%\usepackage[empty]{fullpage}	% Pleine page
%\usepackage{nopageno}		% Pagination
%\usepackage{multirow}		% Tableau complexe
%\usepackage{caption}
%\usepackage{array}


\title{Algorithmique Combinatoire\\Problème du voyageur de commerce}
\author{\bsc{Boujedli} Najim \and \bsc{Paneri} Jérémy}
\date{Master 1 Informatique\\ 2012 -- 2013}

\begin{document}
\maketitle

\begin{figure}[b]
   \centering\includegraphics[scale=0.2]{ufc.png}
\end{figure}

\thispagestyle{empty}
\newpage


% CONTENU %


\section{Présentation générale}

Ce projet a pour but d'implanter des algorithmes permettant de répondre au problème du voyageur de commerce ; c'est-à-dire de parcourir tous les sommets d'un graphe une seule fois sous forme de cycle, le tout avec un poids total le plus petit possible.

Chaque algorithme fonctionne différemment et a une complexité différente, et le but est de comparer les différents résultats obtenus pour un même graphe. Les graphes générés aléatoirement sont obligatoirement complets, condition requise pour nos algorithmes.\\

\texttt{USAGE : ./menu nombre\_de\_sommets graine\_aleatoire}

\section{Structures de données}

\subsection{Graphe}
Le graphe a été repris du TP précédent. Chacun est créé complet, et est représenté de 1 jusqu'à son nombre de sommets maximum. Il contient une liste doublement chaînée de \texttt{TypVoisins}.


\subsection{Tas}
Le tas a été conçu d'après les consignes données. Il permet de stocker des arêtes de sommets (structure \texttt{TypArete}), et est utile pour déterminer celle ayant le plus petit poids, à sa racine.

Bien que nous l'avions utilisé au départ dans nos premières heuristiques, il ne nous a finalement servi que dans le calcul de l'ARPM. En effet, nous nous sommes rendu compte que dans la majorité des cas, un stockage «à la volée» du minimum était à la fois plus efficace et plus facile à comprendre que la structure de tas.

\subsection{Chemin}
Suite à un conseil fourni dans le PDF expliquant le calcul du chemin optimal, nous avons voulu utiliser une chaîne de caractères pour stocker les différents sommets d'un chemin.

Bien que fonctionnelle, son utilisation s'est avérée plus compliquée que prévu, et un changement a dû se faire à mi-parcours : l'utilisation d'un simple tableau d'entier a permis de simplifier les algorithmes et leur compréhension, tout en ôtant les limitations du code ASCII (limitation du nombre de sommets possibles).

\section{Présentation des algorithmes}


\subsection{Solution optimale}

Le calcul de la solution optimale consiste  à  énumérer tous les cycles possibles du graphe, et ne garder que celui ayant le coût le plus bas. Cette fonction est très coûteuse ($\mathcal{O}(n!)$), de fait elle ne doit être appelée que si le nombre de sommets est peu élevé, arbitrairement plus petit que dix.

Pour chaque sommet, on ajoute récursivement tous ses voisins possibles. Lorsqu'on arrive au bout du chemin, on calcule son poids et on le compare au plus petit stocké jusqu'à  maintenant (via un pointeur) : s'il est plus petit, alors il le remplace.


\subsection{Plus proche voisin}
Le plus proche voisin est une heuristique simple : nous choisissons un sommet du graphe (arbitrairement le premier), et nous recherchons le plus proche voisin de ce sommet, que nous ajoutons à la liste. Nous répétons ensuite l'opération avec le sommet ajouté, jusqu'à ce que tous les sommets aient été parcourus par la boucle.


\subsection{Plus petit détour}
Le plus petit détour commence par construire un cycle entre les trois premiers sommets du graphe. Ensuite, nous devons trouver le sommet permettant de faire le plus petit détour en l'ajoutant au chemin : pour cela, nous devons pour chaque sommet restant calculer le plus petit des détours qu'il ferait s'il était inséré dans la chaîne, et prendre le plus petit parmi ces détours possibles.




\subsection{Parcours d'ARPM}

\subsubsection{Création de l'ARPM}

Notre algorithme de création d'un ARPM est basé sur la méthode de Prim, qui consiste, en résumé,  à  partir d'un sommet arbitraire (nous commençons toujours par le premier du graphe), puis à faire grandir l'arbre en rajoutant l'arête la moins coûteuse possible. Pour déterminer ladite arête, on utilise à chaque itération un tas de toutes les arêtes possibles : la racine est alors la plus économique.

\subsubsection{Parcours en profondeur}

Le chemin résultat de cet algorithme consiste à la liste des sommets obtenue en parcourant l'ARPM précédent en profondeur. L'algorithme utilise une sous-fonction récursive pour effectuer ce parcours.


\subsection{Christofides}

Cet algorithme n'a pas été implanté complètement. Néanmoins nous avons réalisé sa première partie, qui consiste à déterminer quels sont les sommets de degré impair présents dans le graphe.




\end{document}
